#! /usr/bin/env python3
# coding= utf-8

class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

def print_list(head):
    n = head
    while n is not None:
        print(n.val, end=" ")
        n = n.next
    print()

class Solution(object):
    @staticmethod
    def happy_reverse(begin, end):
        prev, cur= begin, begin.next
        begin.next = None
        next = None
        while cur is not end:
            next = cur.next
            cur.next = prev
            prev = cur
            cur = next
        return prev
    def reverseKGroup(self, head, k):
        if None is head or k < 2:
            return head

        i = 0
        k_head = ListNode(None)
        k_tail = k_head
        new_head = ListNode(None)
        new_tail = new_head
        cur = head
        while True:
            k_head.next, k_tail = None, k_head
            for i in range(k):
                if cur:
                    k_tail.next = cur
                    k_tail = cur
                    cur = cur.next
                else:
                    if k_head.next:
                        new_tail.next = k_head.next
                    return new_head.next
            k_tail.next = None
            #print_list(k_head.next)
            _head = self.happy_reverse(k_head.next, None)
            #print_list(_head)
            new_tail.next = _head
            new_tail = k_head.next
            #print_list(new_head.next)
        return new_head.next



head = ListNode(None)
test = [1, 2, 3, 4, 5, 6, 7, 8]
prev = head
for i in test:
    node = ListNode(i)
    prev.next = node
    prev = node


s = Solution()
h = s.reverseKGroup(head.next, 3)
print_list(h)
